'''
  Group 1. Part 2,  3(a)
  Description: crack gruyeres cookies
'''

import math
import sys
import signal
import time

class Timeout(Exception): 
    pass
class StopSearch(Exception): 
    pass  


# Warning: the function performs a brute force attack.
# Input  : three strings representing valid cookies: cookie1, cookie2, cookie3
#          a list of the cookies the body of the cookies you want to forge: NewCookiesBodies
#          an integer as the maximun amount of time trying to find a secret of a particular
#          length expressed in minutes: TimeOut
#          two integers that estimate a range for the length of the cookie secret: lenMin y lenMax
# Output:  a list of forged cookies
def forgeCookies(cookie1, cookie2, cookie3, NewCookiesBodies, TimeOut, lenMin, lenMax):
  NewCookies = []
  try:
        TimeOut = TimeOut * 60

  	p = cookie1.find('|')	
	hashCookie1 = cookie1[:p]
	bodyCookie1 = cookie1[p+1:]
	
	p = cookie2.find('|')	
	hashCookie2 = cookie2[:p]
	bodyCookie2 = cookie2[p+1:]
        
	p = cookie3.find('|')	
	hashCookie3 = cookie3[:p]
	bodyCookie3 = cookie3[p+1:]
        
        def c_mul(a, b):
          return eval(hex((long(a) * b) & 0xFFFFFFFFL)[:-1])

        def forgeHash(secret, plainStr):
          if not plainStr:
            return 0
          hSecret = hash(secret)
          value = hSecret ^ len(secret)
          for char in plainStr:        
            value = c_mul(1000003, value) ^ ord(char)
          value = value ^ len(secret + plainStr)
          if value == -1:
              value = -2
          return value
  
	def checkHash(secret):
		m1 = str(hash(secret + bodyCookie1) & 0x7FFFFFF)
		m2 = str(hash(secret + bodyCookie2) & 0x7FFFFFF)
		m3 = str(hash(secret + bodyCookie3) & 0x7FFFFFF)
		if (m1 == hashCookie1 and m2 == hashCookie2 and m3 == hashCookie3):
			print "match [" + secret + "]"
			elapsed = (time.time() - start)
			print "time: " + str(elapsed)
                        for cookieBody in NewCookiesBodies:
                          NewCookies.append(str(forgeHash(secret,cookieBody) & 0x7FFFFFF) + "|" + cookieBody)
                          print "cookieAdded for " + cookieBody
                        raise StopIteration()
                    
	easyRange = [32,33,36,42,43] + range(48, 58) + range(65, 91) + range(97, 123)
        # allRange = range(32,127)

        def recurse(width, position, baseString):
          for char in easyRange:
            if (position < width - 1):
              recurse(width, position + 1, baseString + "%c" % char)
            checkHash(baseString + "%c" % char)

	def timeout_handler(signum, frame):
          raise Timeout()

        signal.signal(signal.SIGALRM, timeout_handler)
        
        start = time.time()
        maxChars = lenMax
        for baseWidth in range(lenMin, maxChars + 1):
          try:         
            print "checking secrets with width [" + `baseWidth` + "]"
            signal.alarm(TimeOut)
            recurse(baseWidth, 0, "")
          except Timeout:
            print "time out!"

        return NewCookies
  
  except StopIteration:
    return NewCookies


#### Test-run EXAMPLE: 
  
# C = forgeCookies("51292534|pepe||author", "4027247|maria||author", "74150387|pedro||author", ["brie|admin|author","queso|admin|author"], 12,7,8)
# for c in C:
#   print c


